package com.lsa.letcode.the105.btFromPreorderInorder;

import java.util.ArrayList;
import java.util.List;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * 
 * HINTS:
 * 	1) find root in inorder
 * 	2) recurse into both parts - left and right subtrees
 *  3) use indeces, not index + length for subarrays.
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
	private TreeNode buildTree(int[] preorder, int preStart, int preStop,
			int[] inorder, int inStart, int inStop) {
		if (preStart > preStop || inStart > inStop) {
			return null;
		}
//		System.out.println(Arrays.toString(Arrays.copyOfRange(preorder,
//				preStart, preStop + 1))
//				+ " "
//				+ Arrays.toString(Arrays.copyOfRange(inorder, inStart,
//						inStop + 1)));
		int headVal = preorder[preStart];
		int i = inStart;
		for (;i <= inStop; i++) {
			if (inorder[i] == headVal) {
				break;
			}
		}
		if (i == inStop + 1) {
			throw new IllegalArgumentException("i != inStop + 1");
		}
		
		TreeNode n = new TreeNode(headVal);
		int diff = inStart - preStart;
		n.left = buildTree(preorder, preStart + 1, i - diff, inorder, inStart, i - 1);
		n.right = buildTree(preorder, i - diff + 1, preStop, inorder, i + 1, inStop);
		
		/*
		 * n.left = buildTree(preorder, preStart + 1, (i - diff) - (inStart - diff) + 1 - 1, inorder, inStart, i - inStart + 1 - 1);
		n.right = buildTree(preorder, i - diff + 1, preStop - (i - diff + 1) + 1, inorder, i + 1, inStop - (i + 1) + 1);
		 * */
    	return n;
    }
    
    public List<Integer> preorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	preorderRec(n, l);
    	return l;
    }
    
    private void preorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		l.add(n.val);
    		preorderRec(n.left, l);
    		preorderRec(n.right, l);
    	}
    }
    
    public List<Integer> inorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	inorderRec(n, l);
    	return l;
    }
    
    private void inorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		inorderRec(n.left, l);
    		l.add(n.val);
    		inorderRec(n.right, l);
    	}
    }
}